COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\def\fnc#1{\mathop{\rm #1}\nolimits}
\baselineskip 14pt
\rm
\line{\sevenrm a03.tex[154,phy] \today\hfill}


\medskip
\ctrline{\bf Earley's Algorithm for Context-Free Language Recognition
and Parsing}

\bigskip
We are given a context-free grammar, $G$; it need not be in any standard
form. We are given a string, stored in $A[1]\hbox{ . . }A[N]$. As a sentinel,
we store an end-of-file marker \#\ in $A[N+1]$.

In the course of the algorithm, we maintain an array $B[0$ . . $N+1]$.
Each element $B↓i$ is a set of ordered pairs; each ordered pair is of the
form $\langle C→u.v,j\rangle$, where $C→uv$ is a production of~$G$.
This ordered pair, as an element of $B↓i$, means that after scanning
the first $j$~characters of~$A$, we decided to look for a string derived
from~$C$, starting with the production $C→uv$; and that we have succeeded
in deriving $A[i+1\hbox{ . . }j]$ from~$u$. We introduce an extra production
$N→S\#$ to the grammar, where $N$ is a new variable.
We initialize the algorithm by setting $i=0$, $B↓0=\{\langle N→.S\#,0\rangle\}$.
Then we do the following steps for successive values of~$i$. 

\bigskip
\noindent
Loop: ($\ast$ Closure $\ast$)

\smallskip
For each element $\langle P→v.Qw,j\rangle\in B↓i$, with $Q\in V$,
find every $Q$-production $Q→x$, and enter $\langle Q→.x,i\rangle$
into~$A↓i$, if it is not already included. The idea is: if looking
for a string derived from $P$ starting at $A[j+1]$ requires looking
for a string derived from $Q$ starting at $A[i+1]$, then we will look
for one derived from~$x$. If we find one, we will accept it as the string
derived from~$Q$.

\vfill

\noindent
($\ast$ Advance $\ast$)

\smallskip
For each element $\langle P→v.Cw,j\rangle\in B↓i$, with $A↓{i+1}=C\in T$,
enter $\langle p→vC.w,j\rangle$ into $B↓{i+1}$.
If no entries are made, announce a syntax error. Increase $i$ by~1.

\smallskip
\noindent
($\ast$ Process Completed Predictions $\ast$)

For each element $\langle P→v.\,,j\rangle\in B↓i$, find each
element $\langle R→x.Py,k\rangle\in B↓j$; enter
$\langle R→xP.y,k\rangle$ into~$A↓i$ if it is not already included.
If $\langle N→S\#.,0\rangle$ is in~$A↓i$, we are finished. Otherwise,
go back to Loop.

\eject

\halign{\lft{#}\cr
$N→S\#$\cr
$S→T\,|\,S+T$\cr
$T→F\,|\,T\ast F$\cr
$F→a\,|\,b\,|\,(S)$\cr}

$$\vcenter{\halign{$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}\quad$
&$\ctr{#}$\cr
0&&1&&2&&3&&4&&5&&6&&7&&8&&9&&10\cr
&a&&+&&b&&\ast&&(&&a&&+&&b&&)&&\#\cr}}$$

\medskip
\disleft 20pt:\phantom{1}0:\quad$N→.S\#,0\quad /\quad S→.T,0\quad /\quad S→.S+T,
0\quad /\quad T→.F,0\quad /\quad T→.T\ast F,0\quad /$
\disleft 50pt::$F→.a,0\quad /\quad F→.b,0\quad /\quad F→.(S),0\quad /$

\medskip
\disleft 20pt:\phantom{1}1:\quad $F→a.,0\quad /\quad T→F.,0\quad /\quad 
S→T.,0\quad /\quad T→T.\ast F,0\quad /\quad N→S.\#,0\quad /$
\disleft 50pt::$S→S.+T,0\quad /$

\medskip
\disleft 20pt:\phantom{1}2:\quad 
$S→S+.T,0\quad /\quad T→.F,2\quad /\quad T→.T\ast F,2\quad /\quad F→.a,2\quad
/\quad F→.b,2\quad /$
\disleft 50pt::$F→.(S),2\quad /$

\medskip
\disleft 20pt:\phantom{1}3:\quad 
$F→b.,2\quad //\quad T→F.,2\quad /\quad S→S+T.,0\quad /\quad T→T.\ast F,2\quad /$

\medskip
\disleft 20pt:\phantom{1}4:\quad 
$T→T\ast .F,2\quad //\quad F→.a,4\quad /\quad F→.b,4\quad /\quad F→.(S),4$

\medskip
\disleft 20pt:\phantom{1}5:\quad 
$F→(.S),4\quad //\quad S→.T,5\quad /\quad S→.S+T,5\quad /\quad T→.F,5\quad
/\quad T→.T\ast F,5\quad /$
\disleft 50pt::$F→.a,5\quad /\quad F→.b,5\quad /\quad F→.(S),5\quad /$

\medskip
\disleft 20pt:\phantom{1}6:\quad 
$F→a.,5\quad //\quad T→F.,5\quad /\quad S→T.,5\quad /\quad 
T→T.\ast F,5\quad /\quad S→S.+T,5\quad /$

\medskip
\disleft 20pt:\phantom{1}7:\quad 
$S→S+.T,5\quad //\quad T→.F,7\quad /\quad T→.T\ast F,7\quad /\quad F→.a,7\quad
/\quad F→.b,7\quad /$
\disleft 50pt::$F→.(S),7$

\medskip
\disleft 20pt:\phantom{1}8:\quad 
$F→b.,7\quad //\quad T→F.,7\quad /\quad T→T.\ast F,7\quad /\quad S→S+T.,5\quad
/\quad F→(S.),4\quad /$
\disleft 50pt::$S→S.+T,5$

\medskip
\disleft 20pt:\phantom{1}9:\quad 
$F→(S).,4\quad //\quad T→T\ast F.,2\quad /\quad S→S+T.,0\quad /\quad 
T→T.\ast F,2\quad /\quad N→S.\#,0$

\medskip
\disleft 20pt:10:\quad 
$N→S\#.,0$

\vfill\eject\end